/*
day124
2019.12.30
*/
#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    	if(matrix.size()==0) return false;
    	
        int h=matrix.size(),l=matrix[0].size();
        
        int L=1,R=(h-1) * l + matrix[matrix.size()-1].size();
        int mid;
        int x,y;
        while(L<=R)
        {
        	mid=L+(R-L)/2;
        	x=(mid-1)%l;
        	y=mid/l-1;
        	if(mid%l!=0) y++;
        	
//        	cout<<x<<'\t'<<y<<endl;
        	
        	if(matrix[y][x] == target) return true;
        	
        	if(matrix[y][x] < target) L=mid+1;
        	
        	else
        	{
        		R=mid-1;
			}
		}
		
		return false;
    }
};


int main()
{
	vector<vector<int> > vec={{1}};
	int target=0;
	Solution s;
	cout<<s.searchMatrix(vec,target);
	return 0;
}
